function radixSort(arr) {
  let max = Math.max(...arr);
  let exp = 1;
  while (max / exp > 0) {
    arr = countingSort(arr, exp);
    exp *= 10;
  }
  return arr;
}

function countingSort(arr, exp) {
  let n = arr.length;
  let output = Array(n).fill(0);
  let count = Array(10).fill(0);

  for (let i = 0; i < n; i++) {
    count[Math.floor((arr[i] / exp) % 10)]++;
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  for (let i = n - 1; i >= 0; i--) {
    output[count[Math.floor((arr[i] / exp) % 10)] - 1] = arr[i];
    count[Math.floor((arr[i] / exp) % 10)]--;
  }

  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }

  return arr;
}

function test() {
    let arr = [329, 457, 657, 839, 436, 720, 355];
    console.log("unsorted array: ", arr)
    let sortedArr = radixSort(arr)
    console.log("sorted array: ", sortedArr)
}

test()